以前の記事, エルガマル暗号では, エルガマル暗号に関する諸々の前提の説明と, その実装について示した. 同エントリ内で, フェルマーの小定理¹については取り扱ったものの, その一般形であるオイラーの定理およびカーマイケルの定理について特に触れなかったため, 本エントリでそれらに関してまとめる. しばしば値の確認には, 簡単のため Haskell を使う.

オイラーの定理

いま, フェルマーテストを定義したとき, \(FT_n(a)\) をパスするには(すなわち, フェルマーの小定理が示す合同式が成り立つには), 要件として, 既約剰余類郡 \(\mathbb{Z}^{\ast}_n\) の各要素と \(^\exists a\ \in\mathbb{Z}\) の積が全て異なり, \(\bmod n\) の既約代表系のすべての積と合同でなければならない. たとえば, 法 \(n=8\) による合同関係で構成する剰余類の完全代表系²は \(0,1,2,3,4,5,6,7\) であるが, \(a=2\) としてしまうと, 既約剰余類郡が構成できていないので, 次のようにしても完全代表系が得られない(積をわざわざ示していないが, 非合同でないことは, 各要素の積が全て異なっていない時点で明白である).

Prelude> [x * 2 `rem` 8 | x <- [0..7]]
[0,2,4,6,0,2,4,6]

そこで, 先に述べた剰余類の既約代表系を考える. これは \(\phi(8)=4\) 個³で, \(1,3,5,7\) である. これを同じように, \(\left\{1\cdot a,\ 3\cdot a,\ 5\cdot a,\ 7\cdot a\right\}\) とし, 先の要件を確認すると, この補題2より, \(\bmod 8\) で全体として \(\left\{1,3,5,7\right\}\) と一致していて, \[1\cdot 3\cdot 5\cdot 7\equiv 1\cdot 3\cdot 5\cdot 7\cdot a^4\pmod{8}\label{eq:first}\tag{1}\] \(\gcd(1\cdot 3\cdot 5\cdot 7,8)=1\) だから, \(1\cdot 3\cdot 5\cdot 7\) を約して, \[a^4\equiv 1\pmod{8}\label{eq:second}\tag{2}\] これは, \(\gcd(a,n)=1\) ということの他に, \(a\) および \(n\) の値に依存した論ではない. すなわち,

がいえる⁴.

*Main> euler'sTheorem n = [a `modExp` (totient n) $ n | a <- [2..], gcd a n == 1]
*Main> all (==1) $ take 100 $ euler'sTheorem 8
True

\(n\) が素数 \(p\) であるとき, \(\phi(p)=p-1\) で, フェルマーの小定理¹となる⁵.

ラグランジュの定理

いま述べたオイラーの定理は, ラグランジュの定理を使っても証明できる. ラグランジュの定理は,

である.

証明: 有限郡 \(G\) の部分郡 \(H\) による類別が \(\displaystyle G=\bigcup_i^r a_iH\) であるとき, \(\mid G\mid=r\mid H\mid\) といえる. この \(r\) は \(r=\mid G:H\mid\) そのものなので, \(\mid G\mid\ =\ \mid G:H\mid\mid H\mid\). \(\square\)

ごく直感的な定理である. これを使えば, オイラーの定理は次のように証明できる.

補題1: 有限郡 \(G\) とその元 \(^\forall g\in G\) に対し, \(g^{\mid G\mid}=e\). \(e\in G\) は単位元.

証明: 巡回部分郡 \(H=\lt g\gt\) の元 \(g\) の位数 \(\mid H\mid\) は, 巡回して \(g^i=e\) となる最小の \(i\in\mathbb{N}\) であるといえる. すなわち \[g^{\mid H\mid}=e\] ここで, 商集合の位数を両辺に次のように与える. \[\left(g^{\mid H\mid}\right)^{\mid G:H\mid}=(e)^{\mid G:H\mid}\] 左辺は指数法則により, また右辺は単位元の繰り返しだから, これを次のようにかける. \[g^{\mid H\mid\mid G:H\mid}=e\] ラグランジュの定理より \[g^{\mid G\mid}=e\] \(\square\)

オイラーの定理の証明: オイラーの定理を仮定したとき, 脚注²より剰余類 \(\overline{a}\) は法 \(n\) に関する既約剰余類郡 \(\mathbb{Z}^{\ast}_{n}\) に含まれる. \(\mid\mathbb{Z}^{\ast}_{n}\mid=\phi(n)\) だから補題 1 より \(\overline{a}^{\phi(n)}=\overline{a^{\phi(n)}}=\overline{1}\). \(\square\)

カーマイケルの定理

オイラーの定理で用いる \(\phi\) 関数は, \(a^{m}\equiv 1\pmod{n}\ (m\in{N}, \gcd(a,n)=1\) を成立させる最小の整数 \(m\) を持ち得ない. たとえば, \(n=8\) では, 先の通り確かに \(m=\phi(8)=4\) で合同式が満足できたが, \(m=2\) としても, これを満足できる.

*Main> all (==1) $ take 100 $ [a `modExp` 2 $ 8 | a <- [2..], gcd a 8 == 1]
True

カーマイケルの \(\lambda\) 関数は, 与えられた整数 \(n\) に対して同合同式を満足する最小の \(m\) を定義より自明に与える.

実装して確かめよう.

*Main> let carmichael'sLambda n = head [k | k <- [1..], and [(m `modExp` k $ n) < 2 | m <- [1..n] gcd m n < 2]]
*Main> let carmichael'sTheorem n = [a `modExp` (carmichael'sLambda n) $ n | a <- [2..], gcd a n == 1]
*Main> all (==1) $ take 100 $ carmichael'sTheorem 8
True